package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-06 01:42
 */
public class Pro0214 {
    //暴力
    public String shortestPalindrome(String s) {
        int len;
        if(s == null || (len = s.length()) == 0) return "";
        StringBuilder sb1 = new StringBuilder(s);
        StringBuilder sb2 = new StringBuilder(s);
        sb2.reverse();
        int i = 0;
        for(; i < len; i++) {
            if(sb1.charAt(i) != sb2.charAt(len - 1 - i)){
                break;
            }
        }

        return sb2.append(s.substring(i-1, len)).toString();
    }


    /**
     * 爆空间
     * @param s
     * @return
     */
    public String shortestPalindrome2(String s) {
        int len;
        if(s == null || (len = s.length()) == 0) return "";

        boolean[][] dp = longestPalindrome(s);
        //寻找原字符串s, [0,..,i] 最长的回文串，通过判断dp[0][i]为true时i的最大值即可。
        int i = len - 1;
        for(; i>=0; i--) {
            if(dp[i][0]) {
                break;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int j = len - 1; j > i; j--) {
            sb.append(s.charAt(j));
        }
        return sb.append(s).toString();
    }

    public boolean[][] longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int start = 0, end = 0;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j <= i; j++) {
                if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[i-1][j+1])) {
                    dp[i][j] = true;
                }
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        Pro0214 pro0214 = new Pro0214();
        System.out.println(pro0214.shortestPalindrome("aacecaaa"));
    }
}
